package j2024.j202408;

public class j0818 {
    /**
     * 647. 回文子串
     * @param s
     * @return
     */
    public int countSubstrings(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int ret  = 0;
        for (int i = n-1; i >=0 ; i--) {
            for (int j = i; j < n; j++) {
                if(s.charAt(i)==s.charAt(j)){
                    dp[i][j] = i+1<j ? dp[i+1][j-1]:true;
                }
                if(dp[i][j] == true){
                    ret++;
                }
            }
        }
        return  ret;
    }

    /**
     * 5. 最长回文子串
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int begin =0,len = 1;
        for (int i = n-1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                if(s.charAt(i)==s.charAt(j)){
                    dp[i][j] = i+1<j ? dp[i+1][j-1]:true;
                }
                if(dp[i][j] && j-i+1>len){
                    len = j-i+1;
                    begin = i;
                }
            }
        }
        return s.substring(begin,begin+len);
    }

    /**
     * 1745. 分割回文串 IV
     * @param s
     * @return
     */
    public boolean checkPartitioning(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        for(int i = n-1;i>=0;i--){
            for(int j = i;j<n;j++){
                if(s.charAt(i)==s.charAt(j)){
                    dp[i][j] = i+1<j?dp[i+1][j-1]:true;
                }
            }
        }
        for(int i  = 1;i<n-1;i++){
            for(int j = i;j<n-1;j++){
                if(dp[0][i-1] && dp[i][j] && dp[j+1][n-1]){
                    return true;
                }
            }
        }
        return false;
    }
}
